#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<stack>
#include<list>
#include<queue>
#include<mpi.h>
#include<vector>
int main(int argc, char** argv){
  	int np;
  	int rank;
	int ns;
	int ranks;
  	MPI_Status status;
	FILE * inf;
	FILE * outf;
	long long v,e;
	long long** con;
	long long* icon;
	double* cb;
	long long lc;
	long long lcbuf;
	long long lcsbuf[2];
	double* cbb;
  	// MPI init
  	MPI_Init(&argc, &argv);
  	MPI_Comm_size(MPI_COMM_WORLD, &np);
  	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	ns=np/2;
	if(rank==0){
		lc=ns;
	}
	if(rank>=ns){
		ranks=rank-ns;
	}else{
		ranks=rank;
	}
	//printf("rank %d ranks %d \n",rank,ranks);
	inf=fopen(argv[1],"r");
	if(rank==0){
		outf=fopen(argv[2],"w");
	}
	fscanf(inf,"%lld %lld\n",&v,&e);
	//printf("%lld %lld rank %d\n",v,e,rank);
	if(rank>=ns){
		long long cont[v];
		long long coni,conv;
		coni=0;
		conv=ranks;
		con =new long long*[(v/ns)+1];
		icon=new long long[(v/ns)+1];
		for(long long i=0;i<e;i++){
			long long v1,v2;
			fscanf(inf,"%lld %lld\n",&v1,&v2);
			if((v1%ns!=ranks)&&(i!=e-1)){
				continue;
			}
			if(v1!=conv){
				con[conv/ns]=new long long[coni];
				for(long long j=0;j<coni; j++){
					con[conv/ns][j]=cont[j];
				}
				icon[conv/ns]=coni;
				printf("rank %d read %lld # %lld\n",rank,conv,icon[conv/ns]);
				conv=v1;
				coni=0;
			}
			cont[coni]=v2;
			coni++;
			if(i==e-1){
				con[conv/ns]=new long long[coni];
				for(long long j=0;j<coni; j++){
					con[conv/ns][j]=cont[j];
				}
				icon[conv/ns]=coni;
			}
		}
	}
	fflush(stdout);
	MPI_Barrier(MPI_COMM_WORLD);	
	if(rank<ns){
		//comp node
		//printf("comp rank %d\n",rank);
		cb=new double[v];
		for(long long i=0;i<v;i++){
			cb[i]=0;
		}
		std::stack<long long> st;
		std::list<long long> p[v];
		long long th[v];
		long long d[v];
		std::queue<long long> q;
		double sgm[v];
		long long w;
		long long vi;
		long long csbuf[2];
		long long crbuf[v];
		int crc;
		for(long long s=rank;s<v;s+=ns){
			printf("comp rank %d start src %lld\n",rank,s);
			while(!st.empty()){
				st.pop();
			}
			for(long long i=0;i<v;i++){
				p[i].clear();
				if(i==s){
					th[i]=1;
					d[i]=0;
				}else{
					th[i]=0;
					d[i]=-1;
				}

			}
			while(!q.empty()){
		                q.pop();
		        }
			q.push(s);
			while(!q.empty()){
				vi=q.front();
				st.push(vi);
				q.pop();
				csbuf[0]=rank;
				csbuf[1]=vi;
				printf("comp rank %d start src %lld request %lld\n",rank,s,vi);
				MPI_Send(&csbuf[0], 2, MPI_LONG_LONG, ns+(vi%ns), 0, MPI_COMM_WORLD);
				MPI_Recv(&crbuf[0], v, MPI_LONG_LONG, ns+(vi%ns), 0, MPI_COMM_WORLD, &status);
				MPI_Get_count(&status, MPI_LONG_LONG, &crc);
				printf("comp rank %d start src %lld request %lld get %d\n",rank,s,vi,crc);
				for(long long i=0;i<crc;i++){
					if(d[crbuf[i]]<0){
						q.push(crbuf[i]);
						d[crbuf[i]]=d[vi]+1;
					}
					if(d[crbuf[i]]==d[vi]+1){
						th[crbuf[i]]+=th[vi];
						p[crbuf[i]].push_back(vi);
					}
				}
			}
			for(long long i=0;i<v;i++){
				sgm[i]=0;
			}
			while(!st.empty()){
				w=st.top();
				st.pop();
				for(std::list<long long>::iterator it=p[w].begin();it!=p[w].end(); ++it){
					sgm[*it]+=((th[*it]+0.0)/(th[w]+0.0))*(1+sgm[w]);
				}
				if(w!=s){
					cb[w]+=sgm[w];
				}
			}
		}
		//printf("comp end rank %d\n",rank);
		if(rank==0){
			lc--;
		}else{
			MPI_Send(&rank, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);
		}
		if(rank==0){
			for(int i=0;i<ns-1;i++){
				MPI_Recv(&lcbuf, 1, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status);
				lc--;
			}
			lcsbuf[0]=0;
			lcsbuf[1]=-1;
			for(int i=0;i<=ns-1;i++){
				MPI_Send(&lcsbuf[0], 2, MPI_LONG_LONG, ns+i, 0, MPI_COMM_WORLD);
			}
		}
		if(rank==0){
			cbb=new double[v];
			for(int i=0;i<ns-1;i++){
				MPI_Recv(&cbb[0], v, MPI_DOUBLE, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status);
				for(long long k=0;k<v;k++){
					cb[k]+=cbb[k];
				}
			}
		}else{
			MPI_Send(&cb[0], v, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);
		}
	}else{
		//sto node
		//printf("sto rank %d\n",rank);
		long long srbuf[2];// comp node, request v-->k (-1 means end)
		long long ssbuf[v];
		long long k;
		//pthread_mutex_t bp;
		while(1){
			//pthread_mutex_lock(&bp);
			MPI_Recv(&srbuf[0], 2, MPI_LONG_LONG, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status);
			printf("sto rank %d recv req %lld from %lld\n",rank, srbuf[1], srbuf[0]);
///*
			if(srbuf[1]<0){
				break;
			}
			k=srbuf[1]/ns;
			for(long long i=0;i<icon[k]; i++){
				ssbuf[i]=con[k][i];
			}
//*/
			printf("sto rank %d recv req %lld from %lld send %lld\n",rank, srbuf[1], srbuf[0], icon[k]);
			MPI_Send(&ssbuf[0], icon[k], MPI_LONG_LONG,(int)(srbuf[0]), 0, MPI_COMM_WORLD);
			//pthread_mutex_unlock(&bp);
		}
	}
	fclose(inf);
	if(rank==0){
		for(long long i=0;i<v;i++){
			fprintf(outf,"%lld %lf\n",i,cb[i]);
		}
		fclose(outf);
	}
	MPI_Barrier(MPI_COMM_WORLD);
  	MPI_Finalize();
	return 0;
}
